/*
 * @lc app=leetcode.cn id=88 lang=cpp
 *
 * [88] 合并两个有序数组
 */

#include <limits.h>

#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;

// @lc code=start
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int left = m - 1;           // 第一个数组中的下标
        int right = n - 1;          // 第二个数组中的下标
        int target = m + n - 1;     // 目标数组中的下标

        // 遍历两个数组，将较大值保存到目标数组中
        while (left >= 0 && right >= 0) {
            if (nums1[left] >= nums2[right]) {
                nums1[target--] = nums1[left--];
            } else {
                nums1[target--] = nums2[right--];
            }
        }
        
        // 第一个数组中有剩余元素
        if (left >= 0) {
            while (left >= 0) {
                nums1[target--] = nums1[left--];
            }
        }

        // 第二个数组中有剩余元素
        if (right >= 0) {
            while (right >= 0) {
                nums1[target--] = nums2[right--];
            }
        }

        return;
    }
};
// @lc code=end

